#!/usr/bin/python
from cell import Cell
from node import Node
from util import Util
class Btree:
    @staticmethod
    def createFromRoot(root, degree = 2):
       return Btree(degree).setRoot(root)

    def __init__(self, degree = 2):
        self.__root = None
        self.__degree = degree

    def getRoot(self):
        return self.__root
    def setRoot(self, root):
        self.__root = root
        return self

    def __str__(self):
        return "btree toString:" + str(self.__root)

    def toString(self):
        from visitor import BtreeLayerVisitor
        from visitor import PtrResult
        #return BtreeLayerVisitor(self, PtrResult()).visit().getResult().getFinal()
        return BtreeLayerVisitor(self).visit().getResult().getFinal()

    def find(self, key):
        if self.__root is not None:
            return self.__findNode(self.__root, key)
        #end if
        return None
    #end def
    """
        if node != none :
            cmp key foreach cell in node
            if not found : 
                nextNode = rightMostNode
                if nextNode == none
                    return false
                return call_self(nextNode)
            else if key equal
                return true & data
            else (key > equal)
                nextNode = cell[this].left
                if nextNode == none
                    return false
                return call_self(nextNode)
        #end if
    """
    def __findNode(self, node, key):
        if node is None:
            return None
        cur = 0
        for c in node.getCells():
            cur = cur + 1
            if key > c.getKey():
                continue
            if c.getKey() ==  key:
               return c    #  one cell key == key
            else: # k < c.getKey()
                nextNode = c.getNode()  # for leftTree
                return self.__findNode(nextNode, key)
        #end for

        if cur == node.used(): # no match key in node
            nextNode = node.getBiggestNode() # for rightTree
            return self.__findNode(nextNode, key)
        #end if

        print "Error:", cur, node
        return  None
    #end def

    """
        in : (root, key) ; out : true
        if len(root) == maxCellsNo:
            newN = createLeaf()
            newN.cells.append(root)
            split(newN, 0)
            root = newN;
            insert_nofull(newN, key)
        else: 
            insert_nofull(root, key)

        func: split(node, index):
            subNode = node.getSubNode(index)
            z = subNode.createEmpty()
            move subNode.cells[t+1:] to z:   
                if subNode is Leaf
                    move key
                else
                    move key && treeRefs
            note::  move subNode.biggestNode -> z.biggestNode

            k = subNode.getKey(t)
            node.insertCell(index, k, subNode)
            node.setNodeRef(index + 1, z)
        end func

        func insert_nofull(node, key):
            if node.isLeaf : # no subNode
                insert to node.getCells
            else:
                index = node.findProperPosition(key)
                subNode = node.getSubNode(index)
                if subNode.used() == maxCellsNo:
                    split(node, subNode.used())
                insert_nofull(subNode, key)
        end func
    """
    def insert(self, key):
        if self.__root is None:
            self.__root = Node.createLeaf(self.__degree)
        #end if
        if self.__root.used() == self.__root.getMaxCellsNo():
            newNode = Node.createLeaf(self.__degree)
            newNode.append(None, self.__root) # set newNode to Interior
            self.split(newNode, 0, True)
            self.__root = newNode
            self.insertNoFull(newNode, key)
        else:
            self.insertNoFull(self.__root, key)
    #end def 

    def split(self, node, index, isRighMost):
        if index >= 0 and index < node.used():
            subNode = node.getCell(index).getNode()
            z = subNode.createEmpty()  

            #1.1 move biggestNode from y -> z
            z.setBiggestNode(subNode.getBiggestNode())
            #1.2. copy cells[t+1:] to z
            for i in range(subNode.getDegree(), subNode.used()):
                z.appendCell(subNode.getCell(i))
            #delete subNode [t+1:]
            subNode.deleteAfter(subNode.getDegree())
            
            k = subNode.getCell(subNode.getDegree()-1).getKey()
            d = subNode.getCell(subNode.getDegree()-1).getData()
            #2.1 set k&d to node[index] if isRightMost Mode;
            if isRighMost:
                node.getCell(index).setKey(k)
                node.getCell(index).setData(d)
                #2.1.1 set z to node.biggestNode
                node.setBiggestNode(z)
            #2.2 insert k&d&subNode into index
            else:
                node.insert(index, k, subNode, d)
                #2.2.1 set z into node[index+1]
                node.getCell(index+1).setNode(z)

            #3.1 set y.biggestNode to y[t].subNode()
            subNode.setBiggestNode(subNode.getCell(subNode.getDegree()-1).getNode())
            #3.2 delete the y[t] key, data, subNode  after (k,d, subNode used)
            subNode.deleteCell(subNode.getDegree() -1)
        else:
            print "Maybe split_biggestNode; or Error: index out of range", index, node
        #end if
    #end def

    def insertNoFull(self, node, key):
        if  node.isLeaf() :
            node.insertToLeaf(key)
        else:
            assert node.isLeaf() == False
            i = 0;
            subNode = None
            while (i < node.used()) and (key > node.getCell(i).getKey()):
                i = i + 1
            if i == node.used() : # k > max(node.cells.key)
                subNode = node.getBiggestNode()
                assert subNode is not None
            elif key < node.getCell(i).getKey():
                subNode = node.getCell(i).getNode()
                assert subNode is not None
            else: #key == node.getCell(i).getKey()
                print "Dump Key:", key
                return 

            if subNode.used() == subNode.getMaxCellsNo():
                if i == node.used(): #prepare for
                    node.append(None, subNode) # same as root split, after this: (i == used() -1)
                    node.setBiggestNode(None)
                    self.split(node, i, True)
                else:
                    self.split(node, i, False)

                # after split , the node[i].key changed to subNode[t]
                if key > node.getCell(i).getKey():
                    if i == node.used() -1:
                        subNode = node.getBiggestNode()
                    else :
                        subNode = node.getCell(i+1).getNode()

            self.insertNoFull(subNode, key)
        #end
    #end def


    def __findMin(self, node, cell):
        if node is None or node.used() <= 0:
            return cell
        else:
            cell = node.getCell(0)
            return self.__findMin(cell.getNode(), cell)
    def min(self, default = None):
        return self.__findMin(self.__root, default)
    #end def
    def __findMax(self, node, cell):
        if node is None or node.used() <= 0:
            return cell
        else:
            cell = node.getCell(node.used()-1)
            return self.__findMax(node.getBiggestNode(), cell)
    def max(self, default = None):
        return self.__findMax(self.__root, default)
    #end def
    
    def _mergeAndDelete(self, node, index, y, z, key):
        y.append(node.getCell(index).getKey(), y.getBiggestNode())
        #copy z.cells & z.biggestNode to y
        for c in z.getCells():
            y.append(c.getKey(), c.getNode())
        y.setBiggestNode(z.getBiggestNode())

        if index == node.used() -1 :
            node.setBiggestNode(y)
        else: #index < node.used() -1
           node.getCell(index+1).setNode(y)

        node.deleteCell(index)

        #remove the root node if node.used == 0
        if node == self.__root and node.used() == 0:
            self.__root = y

        return self.__deleteNode(y, key)
    #end def _mergeAndDelete
    def _3a(self, node, index, y, z, key):
        y.append(node.getCell(index).getKey(), y.getBiggestNode())
        y.setBiggestNode(z.getCell(0).getNode())
        node.getCell(index).setKey(z.getCell(0).getKey())
        z.deleteCell(0)
        return self.__deleteNode(y, key)
    
    def _biggest_3a(self, node, index, left, biggest, key):
        biggest.insert(0, node.getCell(index-1).getKey(), left.getBiggestNode())
            
        maxCellOfLeft = left.getCell(left.used()-1)
        node.getCell(index-1).setKey(maxCellOfLeft.getKey())
        left.setBiggestNode(maxCellOfLeft.getNode())

        left.deleteCell(left.used() -1)
        return self.__deleteNode(biggest, key)

    def _deleteNodeMayInSubNode(self, node, index, key):
        subNode = node.getCell(index).getNode()
        if subNode is not None:
            #1.1 y.used = t-1
            if subNode.used() == subNode.getDegree() - 1:
                z = (index == node.used()-1) and node.getBiggestNode() or node.getCell(index+1).getNode()
                if z is not None:
                    #1.1.1 y.used= t-1 & z.used = t-1
                    if z.used() == z.getDegree() - 1:
                        #merge y k z => y , free z, check root.node & delete root
                        return self._mergeAndDelete(node, index, subNode, z, key) 
                    #1.1.2 y.used= t-1 & z.used > t-1
                    else:
                        assert z.used() >= z.getDegree()
                        # append node[i].k, y.biggest to y; set z[0].k to node, del z[0]
                        return self._3a(node, index, subNode, z, key)
                #end if
                print "Error: z is not None in 3a or 3b"
                return None
            #1.2 y.used < t-1
            elif subNode.used() < subNode.getDegree() -1:
                print "Error : must merge to upper before (used<t-1 ??)"
            #1.3 y.used > t-1
            else:
                return self.__deleteNode(subNode, key)
        else: #can not find key
            return None
    #end def 

    def _deleteNodeInBiggest(self, node, index, key):
        subNode = node.getBiggestNode()
        if subNode is not None:
            #1.1 biggestNode.used == t -1 and leftSubNode = node[i-1]
            if subNode.used() == subNode.getDegree() - 1: 
                subNodeLeft = node.getCell(index - 1).getNode()
                if subNodeLeft is not None:
                    #1.1.1 left.used == t -1
                    if subNodeLeft.used() == subNodeLeft.getDegree() - 1:
                        # merget it 
                        return self._mergeAndDelete(node, index-1, subNodeLeft, subNode, key) 
                    #1.1.2 left.used  >= t
                    elif subNodeLeft.used() >= subNodeLeft.getDegree():
                        return self._biggest_3a(node, index, subNodeLeft, subNode, key)
                    #1.1.2 left.used < t -1
                    else:
                        print "Error: subNodeLeft used < t-1"
                        return None
                else:
                    print "Error: subNodeLeft is None in 3a or 3b case"
                    return None
            #1.2 biggestNode.used < t -1
            elif subNode.used() < subNode.getDegree() -1:
                print "Error : must merge to upper before (used<t-1 ??)"
            #1.3 biggestNode.used > t -1
            else: # biggestNode.used > t-1
                return self.__deleteNode(subNode, key)
        else: # can not find key
            return None
    #end def

    def __deleteReplacedKey(self, node, indexOfReplacedKey):
        replacedKey = node.getCell(indexOfReplacedKey).getKey()
        if node.isLeaf():
            node.deleteCell(indexOfReplacedKey)
        else:
            self._deleteNodeInInterior(node, indexOfReplacedKey, replacedKey)
        return replacedKey
    #end def
    def _deleteNodeInInterior(self, node, index, key):
        subNode = node.getCell(index).getNode()
        #1. y.used >= t
        if subNode.used() >= subNode.getDegree():
            replacedKey = self.__deleteReplacedKey(subNode, subNode.used()-1)
            node.getCell(index).setKey(replacedKey)
            return True

        #2. y.used = t -1 
        elif subNode.used() == subNode.getDegree() -1:
            z = (index == node.used()-1) and node.getBiggestNode() or node.getCell(index+1).getNode()
            #2.1 y.used = t-1, z.used = t-1
            if z.used() == z.getDegree() -1:
                return self._mergeAndDelete(node, index, subNode, z, key)
            #2.2 y.used = t-1, z.used > t-1
            elif z.used() > z.getDegree() -1: 
                replacedKey = self.__deleteReplacedKey(z, 0)
                node.getCell(index).setKey(replacedKey)
                return True
            else: #2.3 y.used = t-1, z.used < t-1
                print "Error: y.used = t-1, but z.used < t-1"
                return None
        else: #y.used < t-1
            print "Error: subNode.used < t -1"
        return None
    #end def
    def __deleteNode(self, node, key):
        index = 0
        for c in node.getCells():
            if key < c.getKey():
                return self._deleteNodeMayInSubNode(node, index, key)
            elif key == c.getKey(): #in node
                if node.isLeaf():
                    node.deleteCell(index)
                    return True
                else:
                    return self._deleteNodeInInterior(node, index, key)
            else: #key > c.getKey()
                pass # forward OK
            index  = index + 1

        if index == node.used():
            return self._deleteNodeInBiggest(node, index, key)
        return None
    #end def
    def delete(self, key):
        if self.__root is not None:
            return self.__deleteNode(self.__root, key)
        #end if
        return None
    #end def

import unittest

class TestBtree(unittest.TestCase):
    def testFind(self):
        btree = self.create();
        #print(btree.toString())

        def _findCheck(btree, key, expectInTree = True):
            cell = btree.find(key)
            if expectInTree :
                self.assertIsNotNone(cell)
                self.assertEqual(cell.getKey(), key)
            else:
                self.assertIsNone(cell)
                #print "[%s] is not in btree" % key
        for a in 'MBCDMFGHMJKLMNMPQRSTMVWXYZ':
            _findCheck(btree, a)

        for a in 'AEIOU':
            _findCheck(btree, a, False)

        for c in "0123456789":
            _findCheck(btree, c, False)


    def _insertPrint(self, btree, key):
        btree.insert(key) 
        self.assertEqual(key, btree.find(key).getKey())
        #print "after %s(%d): " % (key, ord(key[0])), btree.toString()
        minCell = btree.min()
        maxCell = btree.max()
        #print "min:", minCell, " max:", maxCell


    def testInsertFromEnd(self):
        btree = Btree()
        self.assertIsNone(btree.find("M"))

        s =  "MOQRSTUVWX"
        for c in s:
            self._insertPrint(btree, c)

    def testInsertFromHeader(self):
        btree = Btree()
        self.assertIsNone(btree.find("M"))

        s = "MOQLKJIHABCDEFG"
        for c in s:
            self._insertPrint(btree, c)

    def testInsertFromMid(self):
        btree = Btree(3)
        self.assertIsNone(btree.find("M"))

        s = "EMWFGHILNOPUJQRSTXKVWYZ"
        for c in s:
            self._insertPrint(btree, c)


    def create(self):
        bc_node = Node.createLeaf()
        bc_node.append("B")
        bc_node.append("C")
        self.assertTrue(bc_node.isLeaf())
        self.assertEqual(bc_node.used(), 2)

        fg_node = Node.createLeaf()
        fg_node.append("F")
        fg_node.append("G")

        jkl_node = Node.createLeaf()
        jkl_node.append("J")
        jkl_node.append("K")
        jkl_node.append("L")

        dh_node = Node.createInterior()
        dh_node.append("D", bc_node)
        dh_node.append("H", fg_node)
        dh_node.setBiggestNode(jkl_node)
        self.assertFalse(dh_node.isLeaf())
        self.assertEqual(dh_node.used(), 2)
        #print( "dh_node : %s"  % dh_node)

        np_node = Node.createLeaf()
        np_node.append("N")
        np_node.append("P")

        rs_node = Node.createLeaf()
        rs_node.append("R")
        rs_node.append("S")

        vw_node = Node.createLeaf()
        vw_node.append("V")
        vw_node.append("W")

        yz_node = Node.createLeaf()
        yz_node.append("Y")
        yz_node.append("Z")

        qtx_node = Node.createInterior()
        qtx_node.append("Q", np_node)
        qtx_node.append("T", rs_node)
        qtx_node.append("X", vw_node)
        qtx_node.setBiggestNode(yz_node)

        root = Node.createInterior()
        root.append("M", dh_node)
        root.setBiggestNode(qtx_node)
        return Btree.createFromRoot(root)

    def testMinNone(self):
        self.assertIsNone(Btree().min())
        self.assertEqual("A", Btree().min("A"))
    def testMaxNone(self):
        self.assertIsNone(Btree().max())
        self.assertEqual("Z", Btree().max("Z"))
    
    def _deletePrint(self, btree, key):
        self.assertTrue(btree.delete(key))
        self.assertIsNone(btree.find(key))
        print "after delete %s(%d): " % (key, ord(key[0])), btree.toString()
    def testDeleteLeafRoot(self):
        root = Node.createLeaf(3)
        root.append("B")
        root.append("C")
        root.append("D")
        btree = Btree.createFromRoot(root, 3)
        self.assertEqual(btree.find("B").getKey(), "B")

        print "btree: ", btree.toString()
        self._deletePrint(btree, "B")
        self._deletePrint(btree, "C")
        self._deletePrint(btree, "D")

    # not in root & int left leaf & leaf.used > t-1
    def testDeleteNotInRoot_InLeftLeaf(self):
        abc = Node.createLeaf(3)
        abc.append("A")
        abc.append("B")
        abc.append("C")

        em = Node.createLeaf(3)
        em.append("O")
        em.append("P")

        root = Node.createInterior(3)
        root.append("M", abc)
        root.setBiggestNode(em)
        btree = Btree.createFromRoot(root, 3)
        print "btree: ", btree.toString()
        self._deletePrint(btree, "A")

    # not in root, in left leaf
    # 3b: leftNode.used == t-1, righNode(biggestNode).used == t-1
    # merge :  merge  y , node[i], z => y ; delete(y) ; free z, check root.node and delete it 
    def testDeleteNotInRoot_InLeftLeaf_3b(self):
        ab = Node.createLeaf(3)
        ab.append("A")
        ab.append("B")

        op = Node.createLeaf(3)
        op.append("O")
        op.append("P")

        root = Node.createInterior(3)
        root.append("M", ab)
        root.setBiggestNode(op)
        btree = Btree.createFromRoot(root, 3)
        print "btree: ", btree.toString()
        self._deletePrint(btree, "A")
    
    # not in root, in left leaf
    # 3a: leftNode.used == t-1, righNode(biggestNode).used >= t
    def testDeleteNotInRoot_InLeftLeaf_3a(self):
        ab = Node.createLeaf(3)
        ab.append("A")
        ab.append("B")

        opq = Node.createLeaf(3)
        opq.append("O")
        opq.append("P")
        opq.append("Q")

        root = Node.createInterior(3)
        root.append("M", ab)
        root.setBiggestNode(opq)
        btree = Btree.createFromRoot(root, 3)
        print "btree: ", btree.toString()
        self._deletePrint(btree, "A")

    #not in root, in biggestNode
    #3a biggestNode.used = t -1, leftNode.used > t
    def testDeleteNotInRoot_InBiggest_3a(self):
        abc = Node.createLeaf(3)
        abc.append("A")
        abc.append("B")
        abc.append("C")

        op = Node.createLeaf(3)
        op.append("O")
        op.append("P")

        root = Node.createInterior(3)
        root.append("M", abc)
        root.setBiggestNode(op)
        btree = Btree.createFromRoot(root, 3)
        print "btree: ", btree.toString()
        self._deletePrint(btree, "O")

    # not in root, in biggestNode 
    # 3b biggestNode.used = t-1, leftNode.used = t-1
    def testDeleteNotInRoot_InBiggest_3b(self):
        ab = Node.createLeaf(3)
        ab.append("A")
        ab.append("B")

        op = Node.createLeaf(3)
        op.append("O")
        op.append("P")

        root = Node.createInterior(3)
        root.append("M", ab)
        root.setBiggestNode(op)
        btree = Btree.createFromRoot(root, 3)
        print "btree: ", btree.toString()
        self._deletePrint(btree, "O")

    # in interior &  y.used >= t
    def testDeleteInRoot_2a(self):
        abc = Node.createLeaf(3)
        abc.append("A")
        abc.append("B")
        abc.append("C")

        op = Node.createLeaf(3)
        op.append("O")
        op.append("P")

        root = Node.createInterior(3)
        root.append("M", abc)
        root.setBiggestNode(op)
        btree = Btree.createFromRoot(root, 3)
        print "btree: ", btree.toString()
        self._deletePrint(btree, "M")

    # in interior &  z.used >= t
    def testDeleteInRoot_2b(self):
        ab = Node.createLeaf(3)
        ab.append("A")
        ab.append("B")

        opq = Node.createLeaf(3)
        opq.append("O")
        opq.append("P")
        opq.append("Q")

        root = Node.createInterior(3)
        root.append("M", ab)
        root.setBiggestNode(opq)
        btree = Btree.createFromRoot(root, 3)
        print "btree: ", btree.toString()
        self._deletePrint(btree, "M")

    # in interior &  z.used = t-1 & y.used = t-1
    # merge it
    def testDeleteInRoot_2c(self):
        ab = Node.createLeaf(3)
        ab.append("A")
        ab.append("B")

        op = Node.createLeaf(3)
        op.append("O")
        op.append("P")

        root = Node.createInterior(3)
        root.append("M", ab)
        root.setBiggestNode(op)
        btree = Btree.createFromRoot(root, 3)
        print "btree: ", btree.toString()
        self._deletePrint(btree, "M")


if __name__ == "__main__":
    suite = unittest.TestSuite([
        unittest.TestLoader().loadTestsFromTestCase(TestBtree), 
    ])
    unittest.TextTestRunner(verbosity=2).run(suite)
